package Date1214;
// 给定数列1, 1, 1, 3, 5, 9, 17, …，从第4 项开始，每项都是前3 项的和。求
// 第20190324 项的最后4 位数字。
public class Demo1 {
    public static void main(String[] args) { // 动态规划 
        int [] dp = new int[20190324]; 
        dp[0] = 1; 
        dp[1] = 1; 
        dp[2] = 1; 
        dp[3] = 3; 
        for (int i = 4; i <=20190323 ; i++) { 
            dp[i] = (dp[i-1] + dp[i-2] +dp[i-3]) % 10000; 
        } 
        System.out.println(dp[20190323]); }
    
}
